import java.util.Scanner;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-10-11
 * Time: 18:04
 */
public class Test_0928 {

    static class TreeNode {
        public char val; // 树得值
        public TreeNode left; // 左树
        public TreeNode right; // 由树

        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 寻找一个数中两个指定点得公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        // 寻找 p 位置
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root, p, stack1);
        // 寻找 q 位置
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, q, stack2);

        // 最大得栈出两个栈得绝对值个元素
        int sz1 = stack1.size();
        int sz2 = stack2.size();
        if (sz1 > sz2) {
            int len = sz1 - sz2;
            while (len != 0) {
                stack1.pop();
                len--;
            }
        } else {
            int len = sz2 - sz1;
            while (len != 0) {
                stack2.pop();
                len--;
            }
        }
        // 共同出栈 相同 为公共祖先
        while (!(stack1.peek().equals(stack2.peek()))) {
            stack1.pop();
            stack2.pop();
        }
        return stack1.peek();
    }

    // 寻找某点在树中得位置（从根到该点得整个路径）
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }

        // 入栈
        stack.push(root);

        //
        if (root == node) {
            return true;
        }

        // 没找到递归调用寻找左树
        boolean flag1 = getPath(root.left, node, stack);
        if (flag1) {
            // 找到了
            return true;
        }
        boolean flag2 = getPath(root.right, node, stack);
        if (flag2) {
            return true;
        }

        // 根以及左右均为找到 弹出当前栈顶元素
        stack.pop();
        return false;
    }


    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            // 没有树
            return null;
        }

        // 其中一个在根 一个在左树或者右树
        if (p == root || q == root) {
            return root;
        }
        // 左树寻找 p q 是否存在
        TreeNode leftNode = lowestCommonAncestor1(root.left, p, q);
        // 右树寻找 p q 是否存在
        TreeNode rightNode = lowestCommonAncestor1(root.right, p, q);

        if (leftNode != null && rightNode != null) {
            // 左树右树都存在 -- 在两侧
            return root;
        } else if (leftNode != null) {
            // q q在同一侧 -- 且 左边出现找到得第一个数 q 或者 q 就是公共祖先
            return leftNode;
        } else if (rightNode != null) {
            // q q在同一侧 -- 且 右边出现找到得第一个数 q 或者 q 就是公共祖先
            return rightNode;
        } else {
            // 两侧都没有 -- 树中没有这个数
            return null;
        }

    }

    public static void print(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) {
            // 注意 while 处理多个 case
            String str = in.nextLine(); // 有空格 使用 nextLine
            TreeNode root = createTree(str);
            //将此根节点进行中序遍历
        }
    }

    public static void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.println(root);
        inorder(root.right);
    }

    public static int i = 0;
    // 创建一个树
    public static TreeNode createTree(String str) {
        // 遍历字符 将每个字符创建
        TreeNode root = null;
        if(str.charAt(i++) != '#') {
            root = new TreeNode(str.charAt(i)); // 创建根
            root.left = createTree(str);   // 创建根得左树
            root.right = createTree(str); //  创建根得右树
        }else {
            i++;
        }
        return root;
    }

}
